"""
3459. 最长 V 形对角线段的长度
困难
相关标签
premium lock icon
相关企业
提示
给你一个大小为 n x m 的二维整数矩阵 grid，其中每个元素的值为 0、1 或 2。

V 形对角线段 定义如下：

线段从 1 开始。
后续元素按照以下无限序列的模式排列：2, 0, 2, 0, ...。
该线段：
起始于某个对角方向（左上到右下、右下到左上、右上到左下或左下到右上）。
沿着相同的对角方向继续，保持 序列模式 。
在保持 序列模式 的前提下，最多允许 一次顺时针 90 度转向 另一个对角方向。


返回最长的 V 形对角线段 的 长度 。如果不存在有效的线段，则返回 0。



示例 1：

输入： grid = [[2,2,1,2,2],[2,0,2,2,0],[2,0,1,1,0],[1,0,2,2,2],[2,0,0,2,2]]

输出： 5

解释：



最长的 V 形对角线段长度为 5，路径如下：(0,2) → (1,3) → (2,4)，在 (2,4) 处进行 顺时针 90 度转向 ，继续路径为 (3,3) → (4,2)。

示例 2：

输入： grid = [[2,2,2,2,2],[2,0,2,2,0],[2,0,1,1,0],[1,0,2,2,2],[2,0,0,2,2]]

输出： 4

解释：



最长的 V 形对角线段长度为 4，路径如下：(2,3) → (3,2)，在 (3,2) 处进行 顺时针 90 度转向 ，继续路径为 (2,1) → (1,0)。

示例 3：

输入： grid = [[1,2,2,2,2],[2,2,2,2,0],[2,0,0,0,0],[0,0,2,2,2],[2,0,0,2,0]]

输出： 5

解释：



最长的 V 形对角线段长度为 5，路径如下：(0,0) → (1,1) → (2,2) → (3,3) → (4,4)。

示例 4：

输入： grid = [[1]]

输出： 1

解释：

最长的 V 形对角线段长度为 1，路径如下：(0,0)。



提示：

n == grid.length
m == grid[i].length
1 <= n, m <= 500
grid[i][j] 的值为 0、1 或 2。
"""
from typing import List


t = [2,0]

class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        #考虑一种情况，然后循环90度即为另一种情况

        def rotate_90_clockwise(matrix):
            # 转置矩阵
            transposed = [[matrix[j][i] for j in range(len(matrix))] for i in range(len(matrix[0]))]
            # 每一行反转
            rotated = [row[::-1] for row in transposed]
            return rotated

        def getLeftTopMaxVLen(grid: List[List[int]]) -> int:
            #从左上到右上
            m = len(grid)
            n = len(grid[0])
            #从右上到左下的最大长度，不包括1，如果包括1可以理解为是旋转90°右上到左下开始的情况
            dp2 = [ [1] * n for  _ in range(m)]
            for i in range(m-1,-1,-1):
                for j in range(n):
                    #默认值
                    # dp2[i][j] = 1
                    #右上存在,查看是否>0
                    if grid[i][j] != 1 and i+1<m and j-1>=0 and dp2[i+1][j-1]>0:
                        if grid[i + 1][j - 1] + grid[i][j] == 2:
                            dp2[i][j] = dp2[i+1][j-1] + 1
            ans = 0
            #记录左上到右下的最大长度
            dp1 = [ [0] * n for  _ in range(m)]
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 1:
                        dp1[i][j] = 1
                    elif i-1>=0 and j-1>=0 and dp1[i-1][j-1]>0:
                        #如果当前符合要求
                        if t[(dp1[i-1][j-1] - 1) % 2] == grid[i][j]:
                            dp1[i][j] = dp1[i-1][j-1] + 1
                    #当前要满足dp1>0才可以，否则不是从1开始，不满足条件
                    if dp1[i][j]>0:
                        ans = max(ans,dp1[i][j] + dp2[i][j] - 1)
            return ans

        #顺时针循环
        r1 = rotate_90_clockwise(grid)
        r2 = rotate_90_clockwise(r1)
        r3 = rotate_90_clockwise(r2)
        return max(getLeftTopMaxVLen(grid),getLeftTopMaxVLen(r1),getLeftTopMaxVLen(r2),getLeftTopMaxVLen(r3))


if __name__ == '__main__':
    print(Solution().lenOfVDiagonal([[2,2,1,2,2],[2,0,2,2,0],[2,0,1,1,0],[1,0,2,2,2],[2,0,0,2,2]]))
    print(Solution().lenOfVDiagonal([[0,2,0],[0,2,0]]))
